package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/1 16:07
 * @Version 1.0
 **/
public class CombinationSumII {

    public List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        getResult(0,0,candidates,target,new ArrayList<Integer>());
        HashSet<String> set = new HashSet<>();
        Iterator<List<Integer>> iterator = result.iterator();
        while (iterator.hasNext()) {
            List<Integer> integers = iterator.next();
            Collections.sort(integers);
            int len = integers.size();
            String str = "";
            for (int i = 0; i < len; i++) {
                str += integers.get(i)+"-";
            }
            System.out.println(str);
            if (set.contains(str)) {
                iterator.remove();
//                result.remove(integers);
            } else {
                set.add(str);
            }
        }
        return result;
    }
    private void getResult(int index, int sum, int[] candidates, int target, ArrayList<Integer> list) {
        if (sum > target) return;
        if (sum == target) {
            result.add(new ArrayList<>(list));
            return;
        }
        if (index >= candidates.length) return;

        // 不选取当前元素，之后也都不选取，所以index +1
        getResult(index+1,sum,candidates,target,list);
        list.add(candidates[index]);

        // 选取当前元素，由于当前元素不可重复选取所以index不改变
        getResult(index+1,sum+candidates[index],candidates,target,list);
        list.remove(list.size()-1);
    }
}
